Implications

  • Hundreds of thousands of validation points

(Pure) parallel sampling with massive GMRFs

  • In all practical cases there are unknown parameters and a massive GMRF, sampling may be required
  • MCMC with multiple chains is relatively straightforward
    • e.g. Evolutionary MCMC, Embarassingly parallel MCMC
  • Extremely little work on parallelising a single chain
  • Take advantage of local Markov property

xix{i,ne(i)}|xne(i)   iV

E(xi|xi)=1Qiij:jiQijxj;   prec(xi|xi)=Qii

Graph colouring


Theorem 3: Any planar map divided into contigious regions can be coloured using at most FOUR colours (Appel and Haken, 1976)

Graph colouring

Theorem 3: Any planar map divided into contigious regions can be coloured using at most FOUR colours (Appel and Haken, 1976)

Parallel (chromatic) Sampling

Improving the chromatic sampler

  • Single-site updating in spatio-temporal systems is a bad idea
  • We can make use of the global Markov property

xAxB|xC

A,B,C and C separating A,B.

  • In typical Bayesian networks, finding A,B and C can be difficult (seed and spawn idea, Gonzales, 2011).

  • With a spatial network, this is remarkably easy using the Kernighan-Lin algorithm for graph partitioning (Kernighan and Lin, 1970).

Kernighan-Lin algorithm


  • Let G(V,E) be a graph, and let V be the set of nodes and E the set of edges.

  • Find a partition of two disjoint, equal-size subsets A,B, such that the sum of the weights of the edges between nodes in A and B is minimized.

  • Setting edge weights = 1, gives a bisection algorithm!